import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 一维数组 + 一维链表数组
 */
public class Graph {
    ArrayList<Node> edgeList;// 链表数组
    public char[] arrayV;// 顶点数组
    public boolean isDirect;// 是否有向图关键字

    public static class Node {
        int srcV; // 起点
        int destV;// 终点
        int weigth;// 权值
        Node next;

        public Node(int srcV, int destV, int weigth) {
            this.srcV = srcV;
            this.destV = destV;
            this.weigth = weigth;
            this.next = null;
        }
    }

    // 初始化
    public Graph(int size, boolean isDirect) {
        this.arrayV = new char[size];
        this.edgeList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            edgeList.add(null);
        }
        this.isDirect = isDirect;
    }

    /**
     * 插入顶点数组
     */
    public void insertArrayV(char[] arrayV) {
        int len = arrayV.length;
        for (int i = 0; i < len; i++) {
            this.arrayV[i] = arrayV[i];
        }
    }

    /**
     * 插入边
     *
     * @param srcV   起点
     * @param destV  终点
     * @param weigth 权值
     */
    public void addEdge(char srcV, char destV, int weigth) {
        // 拿到了起点 下标 和终点的下标
        int src = getEdgeIndex(srcV);
        int dest = getEdgeIndex(destV);
        // 那就遍历是否存在该条变，如果存在就更新weigth 如果不存在就插入新的边
        addEdgeChild(src, dest, weigth);
        if (isDirect) {
            addEdgeChild(dest, src, weigth);
        }
    }

    private void addEdgeChild(int src, int dest, int weigth) {
        Node cur = edgeList.get(src);
        while (cur != null) {
            if (cur.destV == arrayV[dest]) {
                return; // 当前边存在
            }
            cur = cur.next;
        }
        // 当前边不存在 头插法
        Node newNode = new Node(src, dest, weigth);
        newNode.next = edgeList.get(src);
        edgeList.set(src, newNode);
    }

    private int getEdgeIndex(char srcV) {
        int len = arrayV.length;
        for (int i = 0; i < len; i++) {
            if (arrayV[i] == srcV) {
                return i;
            }
        }
        return -1;
    }

    //    private void printGraph() {
//        int len = arrayV.length;
//        for(int i = 0; i < len;i++) {
//            System.out.print(arrayV[i] + "-> ");
//            Node cur = edgeList.get(i);
//            while(cur != null) {
//                System.out.print(cur.destV + " ");
//                cur = cur.next;
//            }
//            System.out.println();
//        }
//    }
    public void printGraph() {
        for (int i = 0; i < arrayV.length; i++) {
            System.out.print(arrayV[i] + "-> ");

            Node cur = edgeList.get(i);
            while (cur != null) {
                System.out.print(cur.destV + "-> ");
                cur = cur.next;
            }
            System.out.println("null");
        }
    }
    public static void main(String[] args) {
        Graph graph = new Graph(3, false);
        char[] arrayV = {'A', 'B', 'C'};
        graph.insertArrayV(arrayV);
        graph.addEdge('A', 'B', 1);
        //System.out.println("fa");    
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);

        graph.printGraph();
    }
}